#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

/*
    求两个字符串的最长公共子序列长度
    helloworld
    helwold
*/
static int cnt = 0;
std::string str1 = "helloworld";
std::string str2 = "helweord";
const int length1 = str1.size();
const int length2 = str2.size();
int **dp = nullptr;
int **path = nullptr;

void recursiveArry(int index1,int index2)
{
    if(index1 < 0 || index2 < 0)
    {
        return;
    }
    if(path[index1][index2] == 1)
    {
        std::cout << str2[index2] << " ";
        recursiveArry(index1-1,index2-1);
    } else if(path[index1][index2] == 2)
    {
        recursiveArry(index1 - 1,index2);
    } else if(path[index1][index2] == 3)
    {
        recursiveArry(index1,index2 - 1);
    }
}
//非递归的动态规划实现
int LCS03(int index1,int index2)
{
    dp[0][0] = str1[0] == str2[0] ? 1 : 0;
    for(int i = 1;i <= index1;i++)
    {
        if(dp[0][0] == 1)
        {
            dp[i][0] = 1;
        }
    }
    for(int j = 1;j <= index2;j++)
    {
        if(dp[0][0] == 1)
        {
            dp[0][j] = 1;
        }
    }
    for(int i = 1;i <= index1;i++)
    {   
        for(int j = 1;j <= index2;j++)
        {
            if(str1[i] == str2[j])
            {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            }
            else
            {
                int result1 = dp[i - 1][j];
                int result2 = dp[i][j -1];
                dp[i][j] = std::max(result1,result2);
            }
        }
    }
    return dp[index1][index2];
}
//发现有子问题被重复求解了，自然想到用dp数组来存储子问题的解，来破除重复求解子问题。
//二维dp数组dp[index1][index2] 表示在此数组下标下的LCS长度
int LCS02(int index1,int index2)
{
    if(index1 < 0 || index2 < 0)
    {
        return 0;
    }
    if(dp[index1][index2] > 0)
    {
        return dp[index1][index2];
    }
    cnt++;
    if(str1[index1] == str2[index2])
    {
        path[index1][index2] = 1;   //对角线
        dp[index1][index2] = LCS02(index1-1,index2-1) + 1;
        return dp[index1][index2];
    } else{
        //情况1，helloworld
        //      helwol
        int result1 = LCS02(index1-1,index2);
        //情况2，helloworld
        //      helwolde
        int result2 = LCS02(index1,index2 - 1);
        if(result1 > result2)
        {
            dp[index1][index2] = result1;
            path[index1][index2] = 2;   //上方
        }
        else
        {
            dp[index1][index2] = result2;
            path[index1][index2] = 3;   //左方
        }
        return dp[index1][index2];
    }
}
int LCS01(std::string str1,int index1,std::string str2,int index2)
{
    
    if(index1 < 0 || index2 < 0)
    {
        return 0;
    }
    cnt++;
    if(str1[index1] == str2[index2])
    {
        return LCS01(str1,index1-1,str2,index2-1) + 1;
    } else{
        //情况1，helloworld
        //      helwol
        int result1 = LCS01(str1,index1-1,str2,index2);
        //情况2，helloworld
        //      helwolde
        int reuslt2 = LCS01(str1,index1,str2,index2 - 1);
        return std::max(result1,reuslt2);
    }
}
int main()
{
    dp = new int*[length1];
    for(int i = 0;i < length1;i++)
    {
        dp[i] = new int[length2];
        for(int j = 0;j < length2;j++)
        {
            dp[i][j] = -1;
        }
    }

    path = new int*[length1];
    for(int i = 0;i < length1;i++)
    {
        path[i] = new int[length2];
        for(int j = 0;j < length2;j++)
        {
            path[i][j] = 0;
        }
    }
  
    //int resultLength = LCS01(str1,str1.size()-1,str2,str2.size()-1);
    int resultLength = LCS02(str1.size()-1,str2.size()-1);

    std::cout << resultLength << std::endl;
    std::cout << "cnt : " << cnt << std::endl;

    for(int i = 0;i < length1;i++)
    {
        for(int j = 0;j < length2;j++)
        {
            if(dp[i][j] == -1)
            {
                std::cout << "*" << " ";
            }
            else
            std::cout << dp[i][j] << " ";
        }
        std::cout << std::endl;
    }

    // for(int i = 0;i < length1;i++)
    // {
    //     for(int j = 0;j < length2;j++)
    //     {
            
    //         std::cout << path[i][j] << " ";
    //     }
    //     std::cout << std::endl;
    // }

    // recursiveArry(length1 - 1,length2 - 1);
}